Congruencia modulo n

En Z:aRb⇔a≡b(n)⇔n∣a−b\text{En }\Z: \quad aRb \Leftrightarrow a\equiv b(n)\Leftrightarrow n\vert a-b

x‾={y∈Z/y=nk+xcon k∈Z}\overline{x} =\{y\in Z/y=nk+x\quad \text{con }k\in \Z \}

Zn={0‾,1‾,2‾,…,n−1‾}\Z_n=\{\overline{0},\overline{1},\overline{2},\ldots,\overline{n-1}\}

∀x,y∈Z:Si x∈a‾(n)∧y∈b‾(n)⇒x+y∈a+b‾(n)\forall x,y\in \Z : \text{Si } x\in\overline{a}(n)\land y\in\overline{b}(n) \rArr x+y \in \overline{a+b}(n)

∀x,y∈Z:Si x∈a‾(n)∧y∈b‾(n)⇒x⋅y∈a⋅b‾(n)\forall x,y\in \Z : \text{Si } x\in\overline{a}(n)\land y\in\overline{b}(n) \rArr x\cdot y \in \overline{a\cdot b}(n)

Funcion de Euler

ϕ(n)=∣{x∈N/x≤n∧mcd(x,n)=1}∣\phi (n) = \lvert \{x\in\N / x\leq n\land \text{mcd}(x,n)=1 \} \rvert

Osea me devuelve cuantos numeros coprimos hay hasta el numero nn

  1. Si pp es un numero primo, entonces: ϕ(p)=p−1\phi(p)=p-1
  2. Si n es un numero natural y p es numero primo: ϕ(pn)=pn⋅(1−1p)ϕ(pn)=pn−1(p−1)\phi(p^n) = p^n\cdot \left(1-\frac{1}{p}\right) \quad \phi(p^n) =p^{n-1}(p-1)
  3. Si n,m∈N y mcd(n,m)=1:ϕ(n⋅m)=ϕ(n)⋅ϕ(m)n,m\in\N \text{ y mcd}(n,m)=1:\phi(n\cdot m)=\phi(n)\cdot \phi(m)

  4. ϕ(n)=n⋅(1−1p1)⋅(1−1p2)⋅⋯⋅⋅(1−1pr)\phi(n)= n\cdot \left(1-\frac{1}{p_1}\right)\cdot \left(1-\frac{1}{p_2}\right)\cdot\cdots\cdot\cdot \left(1-\frac{1}{p_r}\right)

Teorema de Fermat

Se usa para las ecuaciones de congruencia o para calcular las divisiones de numeros demasiado grandes

Si p es primo∧mcd(a,p)=1⇒ap−1≡1(p)\text{Si }p\text{ es primo} \land \text{mcd}(a,p)= 1\rArr a^{p-1}\equiv 1(p)

Este teorema se usa para ir simplificando los exponentes para verificar si el resto de una division cae en una clase

Teorema de Euler-Fermat

Si mcd (a,n)=1⇒aϕ(n)≡1(n)\text{Si mcd } (a,n)=1 \rArr a^{\phi(n)}\equiv 1(n)

Ecuaciones Lineales de Congruencia

a⋅x≡b(n)a\cdot x\equiv b(n)

Sea a⋅x≡b(n).Si mcd (a,n)=1 entonces hay solucion.\text{Sea } a\cdot x\equiv b(n).\qquad \text{Si mcd }(a,n)=1 \text{ entonces hay solucion.}

x=aϕ(n)−1⋅bx=a^{\phi(n)-1}\cdot b

a⋅x≡b(n) tiene solucion ⇔mcd(a,n)∣b y la cantidad de soluciones es mcd(a,n)a\cdot x \equiv b(n) {\small\text{ tiene solucion }} \Leftrightarrow \text{mcd}(a,n)\vert b\quad {\small\text{ y la cantidad de soluciones es }} \text{mcd} (a,n)

Esto sirve tambien para simplificar las ecuaciones, se puede dividir termino a termino por la cantidad de soluciones, luego resolver la ecuacion, y finalmente al resultado de la eq simplificada se le suma el modulo simplificado la cantidad de soluciones que hallamos obtenido.

Si:a⋅c≡b⋅c(n)∧mcd(c,n)=1Entonces a≡b(n)\text{Si}: a\cdot c\equiv b\cdot c(n)\land \text{mcd}(c,n)=1 \quad \text{Entonces }a\equiv b(n)